# Assignment 2 (v1.0)

=begin doc

WGraph - A Graph is made up of vertices and edges between vertices.
In this class, to represent edges, we use an adjacency list to represent a graph.

=end

# Version 1.0 (preview) modified from v2.7 of Graph.rb

# -------------------------------------------------------
# represents a undirected (it's actually bidirectional) weighted graph
class WGraph

	#to keep array of vertices
	attr_reader :vertices

	# class constructor
	def initialize
		@vertices = Array.new
		@createdValues = Array.new
	end

	# checks whether the graph is empty (an empty graph has no vertices)
	def is_empty?
		return vertices == nil || vertices.count == 0
	end
    
	#to count number of vertices in the graph
	def count_v()
		return vertices.length
	end
    
	# checks if the specified Vertex is found in the current WGraph
    def include?(v1)
		return vertices.include?(v1)
	end
    
	#to add new vertex in the graph
	def add_vertex(vertex)
		raise "Value must be a Vertex!" if vertex.class != Vertex
		if @createdValues.include?(vertex.value)
            p "Vertex (" + vertex.value + ") has already been created and will not be created again" 
        else
			@createdValues << vertex.value			
			if vertices.include?(vertex)
				p "add_vertex: " + vertex + " is already in the graph and will not be added again"
			else
	            p "add_vertex: adding vertex (" + vertex.to_s + ") to graph"
				vertices << vertex
			end
		end
		return @vertices
	end

    # takes in a string and returns the vertex in graph that has the same value as input. 
    # or nil if there is no such vertex
    def get_vertex(actor_name) #takes in string (value)  
        vertices.each do |v|
            if ((v.value <=> actor_name) == 0) # v.value will be 0 if the 2 strings are equivalent
                return v
            end
        end
        return nil # no matching vertex found
    end
    
	#to add edge from v1 to v2 - undirected graph
	def add_edge(v1, v2, weight)
		raise "Value must be a Vertex!" if v1.class != Vertex
		raise "Value must be a Vertex!" if v2.class != Vertex
		raise "Vertex must be in the graph" if !include?(v1)
		raise "Vertex must be in the graph" if !include?(v2)
		raise "Vertex "+v2.to_s+" already adjacent vertex of "+v1.to_s+" in the graph!" if v1.adjList.include?(v2)
		raise "cannot add edge to itself" if v1 == v2
        
		if(v1.class == Vertex && v2.class == Vertex && include?(v1) && include?(v2))
			v1.add_edge(v2, weight)
            v2.add_edge(v1, weight) # undirected graph, hence bidirectional relationship
            p "add_edge: adding edge between (" + v1.to_s + ") and (" + v2.to_s + ") of weight " + weight.to_s + " to graph"  # comment this line if desired
		end
	end

    # returns weight value between v1 and v2 or nil if there's no edge between v1 and v2
    def get_edge_weight(v1, v2)
		raise "Value must be a Vertex!" if v1.class != Vertex
		raise "Value must be a Vertex!" if v2.class != Vertex    
		raise "Vertex must be in the graph" if !include?(v1)
		raise "Vertex must be in the graph" if !include?(v2)   
        
        return 0 if v1 == v2
        
        if v1.adjList.include?(v2)
            index = v1.adjList.index(v2) 
            return v1.adjListWeights[index].to_f
        else
            return nil
        end
    end


	#to delete a vertex from the graph
	def delete_vertex(vertex)
		if(vertex.class == Vertex)
			for i in 0..vertices.length-1
				vi = vertices[i]
				if(vi.adjList.include?(vertex))
                    index = vi.adjList.index(vertex) 
                    vi.adjList.delete(vertex)
                    vi.adjListWeights.delete(index) # need to delete from both arrays
				end
			end
			vertex.adjList.each { |adj|
                index = adj.adjList.index(vertex) 
                adj.adjListWeights.delete(index) 
                adj.adjList.delete(vertex)
            }

            vertex.adjList.clear
            vertex.adjListWeights.clear #

			vertices.delete(vertex)
		end
		return @vertices
	end


	# return a string representation of the array
	def inspect
		return to_s
	end

	# returns a string representation of the array
	def to_s
		return @vertices.inspect
	end
end

# -------------------------------------------------------
# represents a Vertex in a directed graph with weights for edges
class Vertex
	# attributes
	attr_accessor:value
	attr_accessor:adjList
    attr_accessor:adjListWeights

    def initialize *args
        case args.size
            when 1
                init_val *args
            else
                error
            end
    end

	def init_val(value)
		@value = value
		@adjList = Array.new
		@adjListWeights = Array.new # weights of edges to each vertex in adjList
		return @value
	end

    # returns closest vertex or nil if there is none
    def closest_vertex
        return nil if (adjListWeights.size == 0)
    
        index_of_closest_adj_vertex = adjListWeights.index(adjListWeights.min)
        return adjList[index_of_closest_adj_vertex]
    end

    # returns index of closest vertex in adjList or nil if there is none
    def closest_vertex_index
        return nil if (adjListWeights.size == 0)
    
        index_of_closest_adj_vertex = adjListWeights.index(adjListWeights.min)
        return index_of_closest_adj_vertex
    end
    
    # returns edge weight of closest vertex or nil if there is none
    def closest_vertex_edge_weight
        return nil if (adjListWeights.size == 0)
    
        return adjListWeights.min
    end
    
	#to add edge to this vertex
	def add_edge(vertex, weight)
		raise "Value must be a Vertex!" if vertex.class != Vertex
		raise "cannot add edge to itself" if vertex == self
		adjList << vertex
        adjListWeights << weight
	end

	# return a string representation of the vertex
	def inspect
		return to_s
	end

	# returns a string representation of the vertex
	def to_s
		s = value.to_s;
		return s;
	end
end

# -------------------------------------------------------
# Represents a Queue - currently not used. Feel free to use this class if desired
class Queue

	# array used to store the values in the queue
	attr_reader :items

	# class constructor
	def initialize
		@items = Array.new
	end

	# dequeue method. if a drawing exists, redraw the canvas
	def dequeue
		value = items.shift
		return value
	end

	# peek method. if a drawing exists, redraw the canvas
	def peek
		return items.first
	end

	# enqueue method. if a drawing exists, redraw the canvas
	def enqueue(value)
		output = items << value
		return output
	end

	# return a string representation of the array
	def inspect
		return to_s
	end

	# returns a string representation of the array
	def to_s
		return @items.inspect
	end

    # checks if queue is empty
	def is_empty?
		if(items.count == 0)
			return true
		else
            return false
        end
	end
    
    # returns the number of elements in the queue
    def count
        return items.count
    end
end

# -------------------------------------------------------
# Represents a Stack - currently not used. Feel free to use this class if desired
class Stack

	# array used to store the values in the stack
	attr_reader :items

	# class constructor
	def initialize
		@items = Array.new
	end

	# pop method. if a drawing exists, redraw the canvas
	def pop
		value = items.shift
		return value
	end

	# peek method. if a drawing exists, redraw the canvas
	def peek
		return items.first
	end

	# push method. if a drawing exists, redraw the canvas
	def push(value)
		output = items.unshift(value)
		return output
	end

	# return a string representation of the array
	def inspect
		return to_s
	end

	# returns a string representation of the array
	def to_s
		return @items.inspect
	end

	# returns the number of items currently in the stack
	def count
		return items.count
	end
end
